package it.unibz.ti2.internetPizzeria.utils;

import it.unibz.ti2.internetPizzeria.entities.Delivery;
import it.unibz.ti2.internetPizzeria.entities.Order;

import java.util.ArrayList;
import java.util.List;

/**
 * Responsible for reordering list of Order objects to optimize delivery route.
 */
public class RouteOptimizer {

	/**
	 * Auxiliary function used in makePermutation() method.
	 * 
	 * @param level
	 *            first parameter
	 * @param a
	 *            second parameter
	 * @return result of function
	 */
	private static int aux(int level, int a) {
		return (a / level + 1);
	}

	/**
	 * Calculates factorial of number
	 * 
	 * @param arg0
	 *            value to be factored
	 * @return factorial of number
	 */
	private static int factorial(int arg0) {
		if (arg0 < 0)
			throw new IllegalArgumentException();
		else if (arg0 == 0)
			return 1;
		else {
			int result = 1;
			for (int i = 2; i <= arg0; i++) {
				result *= i;
			}
			return result;
		}
	}

	/**
	 * Makes permutation on list.
	 * 
	 * @param level
	 *            number of objects in list
	 * @param list
	 *            List of object to make permutation
	 * @param a
	 *            Number of permutation (from 0 to level!-1)
	 * @return ArrayList of objects in some order
	 */
	private static ArrayList<Order> makePermutation(int level,
			List<Order> list, int a) {
		if (level == 0)
			return new ArrayList<Order>();
		else {
			ArrayList<Order> temp = new ArrayList<Order>(list);
			Order tempOrder = temp.remove(0);
			temp = makePermutation(level - 1, temp, aux(level, a));
			temp.add(a - (level * (aux(level, a) - 1)), tempOrder);
			return temp;
		}
	}

	/**
	 * Calculates distance between two points on sphere
	 * 
	 * @param lng1
	 *            first point's longitude in degrees
	 * @param lat1
	 *            first point's latitude in degrees
	 * @param lng2
	 *            second point's longitude in degrees
	 * @param lat2
	 *            second point's latitude in degrees
	 * @return distance between two points on sphere
	 */
	private static double distance(float lng1, float lat1, float lng2,
			float lat2) {
		double alphaRad1 = Math.toRadians(lng1);
		double bethaRad1 = Math.toRadians(lat1);
		double alphaRad2 = Math.toRadians(lng2);
		double bethaRad2 = Math.toRadians(lat2);
		double radius = 6371;
		double temp = 1 - Math.cos(bethaRad1) * Math.cos(bethaRad2)
				* Math.cos(alphaRad2 - alphaRad1) - Math.sin(bethaRad1)
				* Math.sin(bethaRad2);
		double result = 2 * radius * Math.asin(Math.sqrt(temp / 2));
		return result;
	}

	/**
	 * Reorders list of Order objects to optimize delivery route. Method
	 * calculates sequence using distance between points using metric spherical
	 * geometry. It calculates sums for every possibility and chooses
	 * permutation for minimal distance. Optimization uses additional start
	 * point.
	 * 
	 * @param startPointLat
	 *            latitude of start point.
	 * @param startPointLng
	 *            longitude of start point
	 * @param deliveryPre
	 *            list of Order objects to be optimized
	 * @return List of Order objects after optimization
	 */
	public static List<Order> optimize(float startPointLat,
			float startPointLng, List<Order> deliveryPre) {
		if (deliveryPre.size() < 1)
			return new ArrayList<Order>(deliveryPre);
		else
			return optimize(startPointLat, startPointLng, deliveryPre.get(
					deliveryPre.size() - 1).getDelivery().getPositionLat(),
					deliveryPre.get(deliveryPre.size() - 1).getDelivery()
							.getPositionLng(), deliveryPre, false);
	}

	/**
	 * Reorders list of Order objects to optimize delivery route. Method
	 * calculates sequence using distance between points using metric spherical
	 * geometry. It calculates sums for every possibility and chooses
	 * permutation for minimal distance. Optimization uses additional start and
	 * end points.
	 * 
	 * @param startPointLat
	 *            latitude of start point.
	 * @param startPointLng
	 *            longitude of start point
	 * @param endPointLat
	 *            latitude of end point.
	 * @param endPointLng
	 *            longitude of end point.
	 * @param deliveryPre
	 *            list of Order objects to be optimized
	 * @return List of Order objects after optimization
	 */
	public static List<Order> optimize(float startPointLat,
			float startPointLng, float endPointLat, float endPointLng,
			List<Order> deliveryPre) {
		return optimize(startPointLat, startPointLng, endPointLat, endPointLng,
				deliveryPre, true);
	}

	private static List<Order> optimize(float startPointLat,
			float startPointLng, float endPointLat, float endPointLng,
			List<Order> deliveryPre, Boolean flagEnd) {
		List<Order> result = new ArrayList<Order>(deliveryPre);
		double minDistance = Double.MAX_VALUE;

		for (int i = 0; i < factorial(deliveryPre.size()); i++) {
			List<Order> permutation = makePermutation(deliveryPre.size(),
					deliveryPre, i);
			float dist = 0;

			// distance from start point to first order place
			Delivery deliveryOfFirstOrder = permutation.get(0).getDelivery();
			dist += distance(startPointLng, startPointLat, deliveryOfFirstOrder
					.getPositionLng(), deliveryOfFirstOrder.getPositionLat());

			Delivery deliveryStart = null;
			Delivery deliveryEnd = deliveryOfFirstOrder;

			for (int j = 1; j < permutation.size(); j++) {
				deliveryStart = deliveryEnd;
				deliveryEnd = permutation.get(j).getDelivery();
				dist += distance(deliveryStart.getPositionLng(), deliveryStart
						.getPositionLat(), deliveryEnd.getPositionLng(),
						deliveryEnd.getPositionLat());
			}

			if (flagEnd) {
				// distance from start point to first order place
				Delivery deliveryOfLastOrder = permutation.get(
						permutation.size() - 1).getDelivery();
				dist += distance(endPointLng, endPointLat, deliveryOfLastOrder
						.getPositionLng(), deliveryOfLastOrder.getPositionLat());
			}

			if (dist < minDistance) {
				minDistance = dist;
				result = permutation;
			}

		}
		return result;
	}
}
